#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include <assert.h>

#define BLACK   0
#define RED     1
#define LEFT    0
#define RIGHT   1

struct Tnode
{
    int     nValue;
    BOOL    bColor;
    struct Tnode* pChild[2];
    struct Tnode* pParent;
    Tnode()
    {
        nValue          = 0;
        bColor          = BLACK;
        pChild[LEFT]    = this;
        pChild[RIGHT]   = this;
        pParent         = this;
    }
    Tnode(int nValue, BOOL bColor)
    {
        this->nValue        = nValue;
        this->bColor        = bColor;
        this->pChild[LEFT]  = &NilNode;
        this->pChild[RIGHT] = &NilNode;
        this->pParent       = &NilNode;
    }
}NilNode;

typedef struct Tnode* RBTree;

RBTree RBNil = &NilNode;

void RBRotate(RBTree& pTree, RBTree pNode, BOOL bRight)
{
    assert(pNode != RBNil);
    assert(pNode->pChild[!bRight] != RBNil);

    RBTree pChild = pNode->pChild[!bRight];
    
    pChild->pChild[bRight]->pParent = pNode;
    pNode->pChild[!bRight]          = pChild->pChild[bRight];

    pChild->pParent = pNode->pParent;

    pChild->pChild[bRight] = pNode;
    pNode->pParent = pChild;
    
    if (pChild->pParent == RBNil)
    {
        pTree = pChild;
    }
    else
    {
        BOOL bNodeLorR = (pChild->pParent->pChild[LEFT] != pNode);
        pChild->pParent->pChild[bNodeLorR] = pChild;
    }
}

RBTree RBSearch(RBTree pTree, int nValue)
{
    RBTree pNode = pTree;
    
    while (pNode != RBNil)
    {
        if (pNode->nValue == nValue)
            break;
        pNode = pNode->pChild[pNode->nValue < nValue];
    }
    return pNode;
}

RBTree RBNew(int nValue)
{
    RBTree pNode = (RBTree)malloc(sizeof(struct Tnode));

    pNode->nValue           = nValue;
    pNode->bColor           = RED;
    pNode->pChild[LEFT]     = RBNil;
    pNode->pChild[RIGHT]    = RBNil;
    pNode->pParent          = RBNil;

    return pNode;
}

void RBFixColor(RBTree& pTree, RBTree pNode)
{
    while (pNode->pParent->bColor == RED)
    {
        BOOL    bFLorR;
        RBTree  pUncle;
        
        bFLorR  = (pNode->pParent == pNode->pParent->pParent->pChild[RIGHT]);
        pUncle  = pNode->pParent->pParent->pChild[!bFLorR];
        
        if (pUncle->bColor == RED)
        {
            pUncle->bColor = BLACK;
            pNode->pParent->bColor = BLACK;
            pNode = pNode->pParent->pParent;
            pNode->bColor = RED;
        }
        else 
        {
            BOOL bLorR = (pNode == pNode->pParent->pChild[RIGHT]);

            if (bLorR == bFLorR)
            {
                pNode = pNode->pParent;
                pNode->bColor = BLACK;
                pNode->pParent->bColor = RED;
                RBRotate(pTree, pNode->pParent, !bLorR);
            }
            else
            {
                RBRotate(pTree, pNode->pParent, bLorR);
            }
        }
    }
    pTree->bColor = BLACK;
}

void RBInsert(RBTree& pTree, int nValue)
{
    RBTree  pNode   = pTree;
    BOOL    bLorR   = LEFT;

    if (pTree == RBNil)
    {
        pTree = RBNew(nValue);
        pTree->bColor = BLACK;
        return;
    }

    bLorR = pTree->nValue < nValue;
    while (pNode->pChild[bLorR] != RBNil)
    {
        if (pNode->nValue == nValue)
            return;
        pNode = pNode->pChild[bLorR];
        bLorR = pNode->nValue < nValue;
    }
    RBTree pNew = RBNew(nValue);
    pNode->pChild[bLorR] = pNew;
    pNew->pParent = pNode;
    RBFixColor(pTree, pNew);
}

void DelFixColor(RBTree& pTree, RBTree pNode)
{
    BOOL    bRight      = (pNode->pParent->pChild[LEFT] != pNode);
    RBTree  pBrother    = pNode->pParent->pChild[!bRight];

    while (pNode != pTree && pNode->bColor == BLACK)
    {
        bRight      = (pNode->pParent->pChild[LEFT] != pNode);
        pBrother    = pNode->pParent->pChild[!bRight];
        if (pBrother->bColor == RED)
        {
            pBrother->pParent->bColor = RED;
            pBrother->bColor = BLACK;
            RBRotate(pTree, pBrother, bRight);
            continue;
        }
        if (pBrother->pChild[LEFT]->bColor == BLACK && pBrother->pChild[RIGHT]->bColor == BLACK)
        {
            pBrother->bColor = RED;
            pNode = pNode->pParent;
        }
        else if (pBrother->pChild[!bRight]->bColor == BLACK)
        {
            pBrother->pChild[bRight]->bColor = BLACK;
            pBrother->bColor = RED;
            RBRotate(pTree, pBrother, !bRight);
        }
        else
        {
            pBrother->bColor = pBrother->pParent->bColor;
            pBrother->pParent->bColor = BLACK;
            pBrother->pChild[!bRight]->bColor = BLACK;
            RBRotate(pTree, pBrother->pParent, bRight);
            pNode = pTree;
        }
    }
    pNode->bColor = BLACK;
}

RBTree RBMin(RBTree pNode)
{
    assert (pNode != RBNil);
    while (pNode->pChild[LEFT] != RBNil)
    {
        pNode = pNode->pChild[LEFT];
    }
    return pNode;
}

void RBDelete(RBTree pTree, RBTree pNode)
{
    RBTree  pToDel;
    RBTree  pDelChild;
    BOOL    bLorR;

    if (pNode->pChild[LEFT] == RBNil || pNode->pChild[RIGHT] == RBNil)
    {
        pToDel = pNode;
    }
    else
    {
        pToDel = RBMin(pNode->pChild[RIGHT]);
    }

    pDelChild = pToDel->pChild[pToDel->pChild[LEFT] == RBNil];
    
    pDelChild->pParent = pToDel->pParent;

    bLorR = (pToDel->pParent->pChild[LEFT] != pToDel);
    
    pToDel->pParent->pChild[bLorR] = pDelChild;

    if (pToDel != pNode)
    {
        pNode->nValue = pToDel->nValue;
    }

    if (pToDel->bColor == BLACK)
    {
        DelFixColor(pTree, pDelChild);
    }
}